# -*- coding:utf-8
# 5377. 将二进制表示减到 1 的步骤数 显示英文描述
# 用户通过次数62
# 用户尝试次数100
# 通过次数62
# 提交次数114
# 题目难度Medium
# 给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：
#
# 如果当前数字为偶数，则将其除以 2 。
#
# 如果当前数字为奇数，则将其加上 1 。
#
# 题目保证你总是可以按上述规则将测试用例变为 1 。

from typing import List
class Solution:
    def numSteps(self, s: str) -> int:
        stepCnt = 0
        num = int(s,2)
        print(num)
        print(bin(3))
        while num != 1:
            if num%2 == 0:
                num = num / 2
            else:
                num += 1
            stepCnt+=1
        return stepCnt
#
# class Solution:
#     def numSteps(self, s: str) -> int:
#         jige=0
#         s=int(s,2)
#         while s!=1:
#             if s%2==0:
#                 s=s//2
#             else:
#                 s+=1
#             jige=jige+1
#         return jige

# 方法1：从后往前遍历。第一位单独判断，若carry=1，则结果+1。
# 判断思路及图表（非严格真值表，方便理解，加了状态列）如下
# 其中操作通过异或（^）进行判断，进位通过或（or）进行判断：
# 1.有进位，当前为1，则变成0，操作+1，进位为1；
# 2.有进位，当前为0，则变成1，操作+2，进位为1；
# 3.无进位，当前为1，则不变1，操作+2，进位为1；
# 4.无进位，当前为0，则不变0，操作+1，进位为0；
#
# class Solution:
#     def numSteps(self, s: str) -> int:
#         carry, res = 0, 0
#         for i in range(len(s)-1, 0, -1):
#             res = res+2 if carry ^ (s[i] == '1') else res+1
#             carry = 1 if carry or (s[i] == '1') else 0
#         return res+1 if carry else res

res = Solution().numSteps("1111011110000011100000110001011011110010111001010111110001")
print(res)

